一道练习差分的好题

第一眼看到这个题，一个清晰的暴力思路就浮现与脑海之中…… 好吧，暴力是肯定要超时的，但是差分就不会了。因为修改一个长度为m的区间，暴力的复杂度是O(m),但差分的复杂度是O(1)的。

为什么会想到去用差分呢

因为这道题我们是需要把所有数之间的差都变为0，而差分的实现正好于此类似。

那么，具体该怎么做呢？

很简单，如果两个数的差为2，那么我们只需要操作两次即可让这两个数的值相同。所以，我们可以统计出差分数组中的正数的和与负数的和，取其中的最大值就是最少的操作次数了。具体为什么不用管少的那一个，是因为在处理多的那一个的同时少的那一个同样会被处理，且绝对值小的是会被先处理完的。附一下代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>

using namespace std;
int a[100005],s[100005];
int main()
{
    int n,up,down;
    scanf(“%d”,&n);
    for(register int i = 1; i <= n; i++) scanf(“%d”,&a[i]);
    s[1] = a[1];
    for(register int i = 2; i <= n; i++)
    {
        s[i] = a[i] - a[i - 1];
        if(s[i] > 0) up += s[i];
        else down -= s[i];
    }
    printf(“%d\n%d\n”,max(up,down),abs(up - down + 1));
    return 0;
}